package GreedyAlgorithm;

public class UniqueBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }


    public static int process(int n) {
        if (n < 0) {
            return 0;
        }

        if (n == 0) {
            return 1;
        }

        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        int res = 0;

        for (int leftNum = 0; leftNum < n - 1; leftNum++) {
            // 左边子树的形式数目
            int leftWays = process(leftNum);
            // 右边子树的形式数目
            int rightWays = process(n - 1 - leftNum);

            // 左右两边的排列组合数目
            res += leftWays * rightWays;
        }

        return res;
    }

    public static int numTrees(int n) {
        if (n < 2) {
            return 1;
        }

        int[] dp = new int[n + 1];

        dp[0] = 1;

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp[n];
    }
}
